<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>实现最小堆</title>
  </head>
  <body>
    <script type="text/javascript">
      /*
       * “上浮”操作
       * @param array 待调整的堆
       */
      function upAdjust(array) {
        let childIndex = array.length - 1;
        let parentIndex = Math.floor((childIndex - 1) / 2);
        // temp 保存插入的叶子节点值，用于最后赋值
        const temp = array[childIndex];
        while (childIndex > 0 && temp < array[parentIndex]) {
          // 无须真正交换，单向赋值即可
          array[childIndex] = array[parentIndex];
          childIndex = parentIndex;
          parentIndex = Math.floor((parentIndex - 1) / 2);
        }
        array[childIndex] = temp;
      }
      /*
       * “下沉”操作
       * @param array 待调整的堆
       * @param parentIndex 要“下沉”的父节点
       * @param length 堆的有效大小
       */
      function downAdjust(array, parentIndex, length) {
        // temp 保存父节点值，用于最后的赋值
        const temp = array[parentIndex];
        let childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
          // 如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
          if (
            childIndex + 1 < length &&
            array[childIndex + 1] < array[childIndex]
          ) {
            childIndex++;
          }
          // 如果父节点小于任何一个孩子的值，则直接跳出
          if (temp <= array[childIndex]) break;
          //无须真正交换，单向赋值即可
          array[parentIndex] = array[childIndex];
          parentIndex = childIndex;
          childIndex = 2 * childIndex + 1;
        }
        array[parentIndex] = temp;
      }
      /*
       * 构建堆
       * @param array 待调整的堆
       */
      function buildHeap(array) {
        // 从最后一个非叶子节点开始，依次做“下沉”调整
        for (let i = Math.floor((array.length - 2) / 2); i >= 0; i--) {
          downAdjust(array, i, array.length);
        }
      }

      const arr = [1,3,2,6,5,7,8,9,10,0];
      upAdjust(arr);
      console.log(arr); // [0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
      const arr1 = [7,1,3,10,5,2,8,9,6];
      buildHeap(arr1);
      console.log(arr1); // [1, 5, 2, 6, 7, 3, 8, 9, 10]
    </script>
  </body>
</html>
